package leetcode;

import java.util.ArrayList;
import java.util.List;

/**
 * Created by Ghost on 2014/11/26 0026.
 */
public class Triangle {
    public int minimumTotal(List<List<Integer>> triangle) {
        if(triangle==null || triangle.isEmpty())
            return 0;
        int m = triangle.size();
        int[][] w = new int[m][m];
        List<Integer> tm = triangle.get(m-1);
        for(int i=0;i<m;i++){
            w[m-1][i] = tm.get(i);
        }

        int[][] a = new int[m][m];
        for(int i=0;i<m;i++){
            List<Integer> tmp = triangle.get(i);
            for(int j=0;j<=i;j++){
                a[i][j] = tmp.get(j);
            }
        }

        for(int i=m-2;i>=0;i--){
            for(int j=0;j<=i;j++){
                w[i][j] = Math.min(w[i+1][j]+a[i][j],w[i+1][j+1]+a[i][j]);
            }
        }

        return w[0][0];
    }

    public static void main(String[] args){
        Triangle triangle = new Triangle();
        List<Integer> one = new ArrayList<Integer>();
        one.add(1);
        List<Integer> two = new ArrayList<Integer>();
        two.add(3);
        two.add(2);
        List<Integer> three = new ArrayList<Integer>();
        three.add(4);
        three.add(3);
        three.add(2);
        List<Integer> four = new ArrayList<Integer>();
        four.add(5);
        four.add(4);
        four.add(3);
        four.add(2);

        List<List<Integer>> l = new ArrayList<List<Integer>>();
        l.add(one);
        l.add(two);
        l.add(three);
        l.add(four);

        System.out.println(triangle.minimumTotal(l));
    }
}
